package com.example.demo.suanfa_2tree_taolu;

/**
 * @program: java_base
 * @description: 二叉树：找到a和b最早汇聚点
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/27 13:51
 */
public class LowestAncestorDemo {

    /**
     * 使用套路解法
     * 想法入口：给定任意一个节点x，看其下面是否有a b 的汇聚点，包括x节点本身。
     * 1.a b节点的最先汇聚点和 x 无关
     * 1.1 a b 最早汇聚点在 x 左子树上
     * 1.2 a b 最早汇聚点在 x 右子树上
     * 1.3 a 和 b 没有找全
     * 2.x 是 a b 的 最早交汇点
     * 2.1 a 左子树 b 右子树 或者 a 右子树 b 左子树
     * 2.2 x 是 a 节点 b在 左/右子树上 。 x 是b节点 a在左右树上
     * <p>
     * <p>
     * <p>
     * info 属性
     * findA
     * findB
     * Node ans
     */

    class Node {
        int value;
        Node left;
        Node right;

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    class Info {
        boolean findA;
        boolean findB;
        Node ans;

        public Info(boolean findA, boolean findB, Node ans) {
            this.findA = findA;
            this.findB = findB;
            this.ans = ans;
        }
    }

    public Info process(Node x, Node a, Node b) {
        if (x == null) {
            return new Info(false, false, null);
        }
        Info left = process(x.left, a, b);
        Info right = process(x.right, a, b);
        boolean findA = false;
        boolean findB = false;
        if (x == a || left.findA || right.findA) {
            findA = true;
        }
        if (x == b || left.findB || right.findB) {
            findB = true;
        }

        Node ans = null;
        if (left.ans != null){
            ans = left.ans;
        }else if(right.ans != null){
            ans = right.ans;
        }else {
            if (findA && findB){
                ans = x;
            }
        }
        return new Info(findA, findB, ans);
    }


}
